<html><head><meta charset="utf-8"><title>08 HashMap 源码解析  -慕课专栏</title>
			<meta http-equiv="X-UA-Compatible" content="IE=edge, chrome=1">
			<meta name="renderer" content="webkit">
			<meta property="qc:admins" content="77103107776157736375">
			<meta property="wb:webmaster" content="c4f857219bfae3cb">
			<meta http-equiv="Access-Control-Allow-Origin" content="*">
			<meta http-equiv="Cache-Control" content="no-transform ">
			<meta http-equiv="Cache-Control" content="no-siteapp">
			<link rel="apple-touch-icon" sizes="76x76" href="https://www.imooc.com/static/img/common/touch-icon-ipad.png">
			<link rel="apple-touch-icon" sizes="120x120" href="https://www.imooc.com/static/img/common/touch-icon-iphone-retina.png">
			<link rel="apple-touch-icon" sizes="152x152" href="https://www.imooc.com/static/img/common/touch-icon-ipad-retina.png">
			<link href="https://moco.imooc.com/captcha/style/captcha.min.css" rel="stylesheet">
			<link rel="stylesheet" href="https://www.imooc.com/static/moco/v1.0/dist/css/moco.min.css?t=201907021539" type="text/css">
			<link rel="stylesheet" href="https://www.imooc.com/static/lib/swiper/swiper-3.4.2.min.css?t=201907021539">
			<link rel="stylesheet" href="https://static.mukewang.com/static/css/??base.css,common/common-less.css?t=2.5,column/zhuanlanChapter-less.css?t=2.5,course/inc/course_tipoff-less.css?t=2.5?v=201907051055" type="text/css">
			<link charset="utf-8" rel="stylesheet" href="https://www.imooc.com/static/lib/ueditor/themes/imooc/css/ueditor.css?v=201907021539"><link rel="stylesheet" href="https://www.imooc.com/static/lib/baiduShare/api/css/share_style0_16.css?v=6aba13f0.css"></head>
			<body><div id="main">


<div class="main-con hide-menu">
    <!-- 左侧菜单 & 索引 -->
    
    <div class="right-content" style="padding-left: 0px;">
        <div class="container clearfix" id="top" style="width: 1134px; display: block;">
            
            
            <div class="center_con js-center_con l" style="width: 1134px;">
                <div class="article-con">
                                            <!-- 买过的阅读 -->
                        

                    
                    <div class="art-title" style="margin-top: 0px;">
                        08 HashMap 源码解析  
                    </div>
                    <div class="art-info clearfix">
                        
                        <span class="l">
                            更新时间：2019-09-27 12:52:38
                        </span>
                    </div>
                    <div class="art-top">
                                                <img src="https://img4.mukewang.com/5d63579e000121c606400359.jpg" alt="">
                                                                        <div class="famous-word-box">
                            <img src="https://www.imooc.com/static/img/column/bg-l.png" alt="" class="bg1 bg">
                            <img src="https://www.imooc.com/static/img/column/bg-r.png" alt="" class="bg2 bg">
                            <div class="famous-word">自信和希望是青年的特权。<p class="author">——大仲马</p></div>
                        </div>
                                            </div>
                    <div class="art-content js-lookimg">
                        <div id="article_content">
                            <div class="cl-preview-section"><h2 id="引导语" style="font-size: 30px;">引导语</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">HashMap 源码很长，面试的问题也非常多，但这些面试问题，基本都是从源码中衍生出来的，所以我们只需要弄清楚其底层实现原理，回答这些问题就会游刃有余。</p>
</div><div class="cl-preview-section"><h2 id="整体架构" style="font-size: 30px;">1 整体架构</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表，整体的数据结构如下：<br>
<img class="" src="https://img.mukewang.com/5d5fc7cc0001ec3211040928.png" data-original="//img.mukewang.com/5d5fc7cc0001ec3211040928.png" alt="图片描述">图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树，比如数组下标索引为 2 的位置就是一个链表，下标索引为 9 的位置对应的就是红黑树，具体细节我们下文再说。</p>
</div><div class="cl-preview-section"><h3 id="类注释">1.1 类注释</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">从 HashMap 的类注释中，我们可以得到如下信息：</p>
</div><div class="cl-preview-section"><ul>
<li style="font-size: 20px; line-height: 38px;">允许 null 值，不同于 HashTable ，是线程不安全的；</li>
<li style="font-size: 20px; line-height: 38px;">load factor（影响因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 &gt; 需要的数组大小 /load factor；</li>
<li style="font-size: 20px; line-height: 38px;">如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；</li>
<li style="font-size: 20px; line-height: 38px;">HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；</li>
<li style="font-size: 20px; line-height: 38px;">在迭代过程中，如果 HashMap 的结构被修改，会快速失败。</li>
</ul>
</div><div class="cl-preview-section"><h3 id="常见属性">1.2 常见属性</h3>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"> <span class="token comment">//初始容量为 16</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> DEFAULT_INITIAL_CAPACITY <span class="token operator">=</span> <span class="token number">1</span> <span class="token operator">&lt;&lt;</span> <span class="token number">4</span><span class="token punctuation">;</span>

 <span class="token comment">//最大容量</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> MAXIMUM_CAPACITY <span class="token operator">=</span> <span class="token number">1</span> <span class="token operator">&lt;&lt;</span> <span class="token number">30</span><span class="token punctuation">;</span>

 <span class="token comment">//负载因子默认值</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">float</span> DEFAULT_LOAD_FACTOR <span class="token operator">=</span> <span class="token number">0.75f</span><span class="token punctuation">;</span>
 
 <span class="token comment">//桶上的链表长度大于等于8时，链表转化成红黑树</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> TREEIFY_THRESHOLD <span class="token operator">=</span> <span class="token number">8</span><span class="token punctuation">;</span>

 <span class="token comment">//桶上的红黑树大小小于等于6时，红黑树转化成链表</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> UNTREEIFY_THRESHOLD <span class="token operator">=</span> <span class="token number">6</span><span class="token punctuation">;</span>

 <span class="token comment">//当数组容量大于 64 时，链表才会转化成红黑树</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">int</span> MIN_TREEIFY_CAPACITY <span class="token operator">=</span> <span class="token number">64</span><span class="token punctuation">;</span>

 <span class="token comment">//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast</span>
 <span class="token keyword">transient</span> <span class="token keyword">int</span> modCount<span class="token punctuation">;</span>

 <span class="token comment">//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)</span>
 <span class="token keyword">transient</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>

 <span class="token comment">//存放数据的数组</span>
 <span class="token keyword">transient</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> table<span class="token punctuation">;</span>

 <span class="token comment">// 扩容的门槛，有两种情况</span>
 <span class="token comment">// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。</span>
 <span class="token comment">// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75</span>
 <span class="token keyword">int</span> threshold<span class="token punctuation">;</span>

 <span class="token comment">//链表的节点</span>
 <span class="token keyword">static</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> <span class="token keyword">implements</span> <span class="token class-name">Map<span class="token punctuation">.</span>Entry</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> <span class="token punctuation">{</span>
 
 <span class="token comment">//红黑树的节点</span>
 <span class="token keyword">static</span> <span class="token keyword">final</span> <span class="token keyword">class</span> <span class="token class-name">TreeNode</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> <span class="token keyword">extends</span> <span class="token class-name">LinkedHashMap<span class="token punctuation">.</span>Entry</span><span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> <span class="token punctuation">{</span>
</code></pre>
</div><div class="cl-preview-section"><h2 id="新增" style="font-size: 30px;">2 新增</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">新增 key，value 大概的步骤如下：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">空数组有无初始化，没有的话初始化；</li>
<li style="font-size: 20px; line-height: 38px;">如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3；</li>
<li style="font-size: 20px; line-height: 38px;">如果 hash 冲突，两种解决方案：链表 or 红黑树；</li>
<li style="font-size: 20px; line-height: 38px;">如果是链表，递归循环，把新元素追加到队尾；</li>
<li style="font-size: 20px; line-height: 38px;">如果是红黑树，调用红黑树新增的方法；</li>
<li style="font-size: 20px; line-height: 38px;">通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖；</li>
<li style="font-size: 20px; line-height: 38px;">判断是否需要扩容，需要扩容进行扩容，结束。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">我们来画一张示意图来描述下：<br>
<img class="" src="https://img.mukewang.com/5d5fc7e200016af809121188.jpg" data-original="//img.mukewang.com/5d5fc7e200016af809121188.jpg" alt="图片描述">代码细节如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 入参 hash：通过 hash 算法计算出来的值。</span>
<span class="token comment">// 入参 onlyIfAbsent：false 表示即使 key 已经存在了，仍然会用新值覆盖原来的值，默认为 false</span>
<span class="token keyword">final</span> V <span class="token function">putVal</span><span class="token punctuation">(</span><span class="token keyword">int</span> hash<span class="token punctuation">,</span> K key<span class="token punctuation">,</span> V value<span class="token punctuation">,</span> <span class="token keyword">boolean</span> onlyIfAbsent<span class="token punctuation">,</span>
               <span class="token keyword">boolean</span> evict<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值</span>
    Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">;</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> p<span class="token punctuation">;</span> <span class="token keyword">int</span> n<span class="token punctuation">,</span> i<span class="token punctuation">;</span>
    <span class="token comment">//如果数组为空，使用 resize 方法初始化</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>tab <span class="token operator">=</span> table<span class="token punctuation">)</span> <span class="token operator">==</span> null <span class="token operator">||</span> <span class="token punctuation">(</span>n <span class="token operator">=</span> tab<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
        n <span class="token operator">=</span> <span class="token punctuation">(</span>tab <span class="token operator">=</span> <span class="token function">resize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">.</span>length<span class="token punctuation">;</span>
    <span class="token comment">// 如果当前索引位置是空的，直接生成新的节点在当前索引位置上</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>p <span class="token operator">=</span> tab<span class="token punctuation">[</span>i <span class="token operator">=</span> <span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&amp;</span> hash<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span>
        tab<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">newNode</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// 如果当前索引位置有值的处理方法，即我们常说的如何解决 hash 冲突</span>
    <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// e 当前节点的临时变量</span>
        Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> e<span class="token punctuation">;</span> K k<span class="token punctuation">;</span>
        <span class="token comment">// 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>p<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span>
            <span class="token punctuation">(</span><span class="token punctuation">(</span>k <span class="token operator">=</span> p<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>key <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            e <span class="token operator">=</span> p<span class="token punctuation">;</span>
        <span class="token comment">// 如果是红黑树，使用红黑树的方式新增</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>p <span class="token keyword">instanceof</span> <span class="token class-name">TreeNode</span><span class="token punctuation">)</span>
            e <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">)</span>p<span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">putTreeVal</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">,</span> tab<span class="token punctuation">,</span> hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 是个链表，把新节点放到链表的尾端</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
            <span class="token comment">// 自旋</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> binCount <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> <span class="token operator">++</span>binCount<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token comment">// e = p.next 表示从头开始，遍历链表</span>
                <span class="token comment">// p.next == null 表明 p 是链表的尾节点</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> p<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                    <span class="token comment">// 把新节点放到链表的尾部 </span>
                    p<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">newNode</span><span class="token punctuation">(</span>hash<span class="token punctuation">,</span> key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
                    <span class="token comment">// 当链表的长度大于等于 8 时，链表转红黑树</span>
                    <span class="token keyword">if</span> <span class="token punctuation">(</span>binCount <span class="token operator">&gt;=</span> TREEIFY_THRESHOLD <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span>
                        <span class="token function">treeifyBin</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> hash<span class="token punctuation">)</span><span class="token punctuation">;</span>
                    <span class="token keyword">break</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                <span class="token comment">// 链表遍历过程中，发现有元素和新增的元素相等，结束循环</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span>
                    <span class="token punctuation">(</span><span class="token punctuation">(</span>k <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>key <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
                    <span class="token keyword">break</span><span class="token punctuation">;</span>
                <span class="token comment">//更改循环的当前元素，使 p 在遍历过程中，一直往后移动。</span>
                p <span class="token operator">=</span> e<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        <span class="token comment">// 说明新节点的新增位置已经找到了</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>e <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            V oldValue <span class="token operator">=</span> e<span class="token punctuation">.</span>value<span class="token punctuation">;</span>
            <span class="token comment">// 当 onlyIfAbsent 为 false 时，才会覆盖值 </span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>onlyIfAbsent <span class="token operator">||</span> oldValue <span class="token operator">==</span> null<span class="token punctuation">)</span>
                e<span class="token punctuation">.</span>value <span class="token operator">=</span> value<span class="token punctuation">;</span>
            <span class="token function">afterNodeAccess</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">// 返回老值</span>
            <span class="token keyword">return</span> oldValue<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 记录 HashMap 的数据结构发生了变化</span>
    <span class="token operator">++</span>modCount<span class="token punctuation">;</span>
    <span class="token comment">//如果 HashMap 的实际大小大于扩容的门槛，开始扩容</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">++</span>size <span class="token operator">&gt;</span> threshold<span class="token punctuation">)</span>
        <span class="token function">resize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">afterNodeInsertion</span><span class="token punctuation">(</span>evict<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> null<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">新增的流程上面应该已经表示很清楚了，接下来我们来看看链表和红黑树新增的细节：</p>
</div><div class="cl-preview-section"><h3 id="链表的新增">2.1 链表的新增</h3>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">链表的新增比较简单，就是把当前节点追加到链表的尾部，和 LinkedList 的追加实现一样的。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin，此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树，转化成红黑树的过程也比较简单，具体转化的过程源码可以去 github：<a href="https://github.com/luanqiu/java8">https://github.com/luanqiu/java8</a> 上面去查看。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">可能面试的时候，有人问你为什么是 8，这个答案在源码中注释有说，中文翻译过来大概的意思是：</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。</p>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">在考虑设计 8 这个值的时候，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token operator">*</span> <span class="token number">0</span><span class="token operator">:</span>    <span class="token number">0.60653066</span>
<span class="token operator">*</span> <span class="token number">1</span><span class="token operator">:</span>    <span class="token number">0.30326533</span>
<span class="token operator">*</span> <span class="token number">2</span><span class="token operator">:</span>    <span class="token number">0.07581633</span>
<span class="token operator">*</span> <span class="token number">3</span><span class="token operator">:</span>    <span class="token number">0.01263606</span>
<span class="token operator">*</span> <span class="token number">4</span><span class="token operator">:</span>    <span class="token number">0.00157952</span>
<span class="token operator">*</span> <span class="token number">5</span><span class="token operator">:</span>    <span class="token number">0.00015795</span>
<span class="token operator">*</span> <span class="token number">6</span><span class="token operator">:</span>    <span class="token number">0.00001316</span>
<span class="token operator">*</span> <span class="token number">7</span><span class="token operator">:</span>    <span class="token number">0.00000094</span>
<span class="token operator">*</span> <span class="token number">8</span><span class="token operator">:</span>    <span class="token number">0.00000006</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">意思是，当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，几乎不会碰到链表转化成红黑树的情况，毕竟概念只有千万分之一。</p>
</div><div class="cl-preview-section"><h3 id="红黑树新增节点过程">2.2 红黑树新增节点过程</h3>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">
<p style="font-size: 20px; line-height: 38px;">首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：</p>
<p style="font-size: 20px; line-height: 38px;">1.1. 如果节点没有实现 Comparable 接口，使用 equals 进行判断；</p>
<p style="font-size: 20px; line-height: 38px;">1.2. 如果节点自己实现了  Comparable 接口，使用 compareTo 进行判断。</p>
</li>
<li style="font-size: 20px; line-height: 38px;">
<p style="font-size: 20px; line-height: 38px;">新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；</p>
</li>
<li style="font-size: 20px; line-height: 38px;">
<p style="font-size: 20px; line-height: 38px;">自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；</p>
</li>
<li style="font-size: 20px; line-height: 38px;">
<p style="font-size: 20px; line-height: 38px;">把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；</p>
</li>
<li style="font-size: 20px; line-height: 38px;">
<p style="font-size: 20px; line-height: 38px;">进行着色和旋转，结束。</p>
</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">具体源码如下：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">//入参 h：key 的hash值</span>
<span class="token keyword">final</span> TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> <span class="token function">putTreeVal</span><span class="token punctuation">(</span>HashMap<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> map<span class="token punctuation">,</span> Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span> tab<span class="token punctuation">,</span>
                               <span class="token keyword">int</span> h<span class="token punctuation">,</span> K k<span class="token punctuation">,</span> V v<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    Class<span class="token operator">&lt;</span><span class="token operator">?</span><span class="token operator">&gt;</span> kc <span class="token operator">=</span> null<span class="token punctuation">;</span>
    <span class="token keyword">boolean</span> searched <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token comment">//找到根节点</span>
    TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> root <span class="token operator">=</span> <span class="token punctuation">(</span>parent <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">root</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
    <span class="token comment">//自旋</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span>TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> p <span class="token operator">=</span> root<span class="token punctuation">;</span><span class="token punctuation">;</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> dir<span class="token punctuation">,</span> ph<span class="token punctuation">;</span> K pk<span class="token punctuation">;</span>
        <span class="token comment">// p hash 值大于 h，说明 p 在 h 的右边</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>ph <span class="token operator">=</span> p<span class="token punctuation">.</span>hash<span class="token punctuation">)</span> <span class="token operator">&gt;</span> h<span class="token punctuation">)</span>
            dir <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token comment">// p hash 值小于 h，说明 p 在 h 的左边</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>ph <span class="token operator">&lt;</span> h<span class="token punctuation">)</span>
            dir <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token comment">//要放进去key在当前树中已经存在了(equals来判断)</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>pk <span class="token operator">=</span> p<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> k <span class="token operator">||</span> <span class="token punctuation">(</span>k <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> k<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>pk<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> p<span class="token punctuation">;</span>
        <span class="token comment">//自己实现的Comparable的话，不能用hashcode比较了，需要用compareTo</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>kc <span class="token operator">==</span> null <span class="token operator">&amp;&amp;</span>
                  <span class="token comment">//得到key的Class类型，如果key没有实现Comparable就是null</span>
                  <span class="token punctuation">(</span>kc <span class="token operator">=</span> <span class="token function">comparableClassFor</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token operator">||</span>
                  <span class="token comment">//当前节点pk和入参k不等</span>
                 <span class="token punctuation">(</span>dir <span class="token operator">=</span> <span class="token function">compareComparables</span><span class="token punctuation">(</span>kc<span class="token punctuation">,</span> k<span class="token punctuation">,</span> pk<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>searched<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> q<span class="token punctuation">,</span> ch<span class="token punctuation">;</span>
                searched <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>ch <span class="token operator">=</span> p<span class="token punctuation">.</span>left<span class="token punctuation">)</span> <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span>
                     <span class="token punctuation">(</span>q <span class="token operator">=</span> ch<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>h<span class="token punctuation">,</span> k<span class="token punctuation">,</span> kc<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span> <span class="token operator">||</span>
                    <span class="token punctuation">(</span><span class="token punctuation">(</span>ch <span class="token operator">=</span> p<span class="token punctuation">.</span>right<span class="token punctuation">)</span> <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span>
                     <span class="token punctuation">(</span>q <span class="token operator">=</span> ch<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span>h<span class="token punctuation">,</span> k<span class="token punctuation">,</span> kc<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span><span class="token punctuation">)</span>
                    <span class="token keyword">return</span> q<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            dir <span class="token operator">=</span> <span class="token function">tieBreakOrder</span><span class="token punctuation">(</span>k<span class="token punctuation">,</span> pk<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> xp <span class="token operator">=</span> p<span class="token punctuation">;</span>
        <span class="token comment">//找到和当前hashcode值相近的节点(当前节点的左右子节点其中一个为空即可)</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>p <span class="token operator">=</span> <span class="token punctuation">(</span>dir <span class="token operator">&lt;=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">?</span> p<span class="token punctuation">.</span>left <span class="token operator">:</span> p<span class="token punctuation">.</span>right<span class="token punctuation">)</span> <span class="token operator">==</span> null<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            Node<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> xpn <span class="token operator">=</span> xp<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token comment">//生成新的节点</span>
            TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span> x <span class="token operator">=</span> map<span class="token punctuation">.</span><span class="token function">newTreeNode</span><span class="token punctuation">(</span>h<span class="token punctuation">,</span> k<span class="token punctuation">,</span> v<span class="token punctuation">,</span> xpn<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">//把新节点放在当前子节点为空的位置上</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>dir <span class="token operator">&lt;=</span> <span class="token number">0</span><span class="token punctuation">)</span>
                xp<span class="token punctuation">.</span>left <span class="token operator">=</span> x<span class="token punctuation">;</span>
            <span class="token keyword">else</span>
                xp<span class="token punctuation">.</span>right <span class="token operator">=</span> x<span class="token punctuation">;</span>
            <span class="token comment">//当前节点和新节点建立父子，前后关系</span>
            xp<span class="token punctuation">.</span>next <span class="token operator">=</span> x<span class="token punctuation">;</span>
            x<span class="token punctuation">.</span>parent <span class="token operator">=</span> x<span class="token punctuation">.</span>prev <span class="token operator">=</span> xp<span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>xpn <span class="token operator">!=</span> null<span class="token punctuation">)</span>
                <span class="token punctuation">(</span><span class="token punctuation">(</span>TreeNode<span class="token operator">&lt;</span>K<span class="token punctuation">,</span>V<span class="token operator">&gt;</span><span class="token punctuation">)</span>xpn<span class="token punctuation">)</span><span class="token punctuation">.</span>prev <span class="token operator">=</span> x<span class="token punctuation">;</span>
            <span class="token comment">//balanceInsertion 对红黑树进行着色或旋转，以达到更多的查找效率，着色或旋转的几种场景如下</span>
            <span class="token comment">//着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色；如果父亲是红色，那么必须通过重新着色或者旋转的方法，再次达到红黑树的5个约束条件</span>
            <span class="token comment">//旋转： 父亲是红色，叔叔是黑色时，进行旋转</span>
            <span class="token comment">//如果当前节点是父亲的右节点，则进行左旋</span>
            <span class="token comment">//如果当前节点是父亲的左节点，则进行右旋</span>
          
            <span class="token comment">//moveRootToFront 方法是把算出来的root放到根节点上</span>
            <span class="token function">moveRootToFront</span><span class="token punctuation">(</span>tab<span class="token punctuation">,</span> <span class="token function">balanceInsertion</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> x<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> null<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">红黑树的新增，要求大家对红黑树的数据结构有一定的了解。面试的时候，一般只会问到新增节点到红黑树上大概是什么样的一个过程，着色和旋转的细节不会问，因为很难说清楚，但我们要清楚着色指的是给红黑树的节点着上红色或黑色，旋转是为了让红黑树更加平衡，提高查询的效率，总的来说都是为了满足红黑树的 5 个原则：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">节点是红色或黑色</li>
<li style="font-size: 20px; line-height: 38px;">根是黑色</li>
<li style="font-size: 20px; line-height: 38px;">所有叶子都是黑色</li>
<li style="font-size: 20px; line-height: 38px;">从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点</li>
<li style="font-size: 20px; line-height: 38px;">从每个叶子到根的所有路径上不能有两个连续的红色节点</li>
</ol>
</div><div class="cl-preview-section"><h2 id="查找" style="font-size: 30px;">3 查找</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">HashMap 的查找主要分为以下三步：</p>
</div><div class="cl-preview-section"><ul>
<li style="font-size: 20px; line-height: 38px;">根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话往下。</li>
<li style="font-size: 20px; line-height: 38px;">判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。</li>
<li style="font-size: 20px; line-height: 38px;">分别走链表和红黑树不同类型的查找方法。</li>
</ul>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">链表查找的关键代码是：</p>
</div><div class="cl-preview-section"><pre class="  language-java"><code class="prism  language-java"><span class="token comment">// 采用自旋方式从链表中查找 key，e 初始为为链表的头节点</span>
<span class="token keyword">do</span> <span class="token punctuation">{</span>
    <span class="token comment">// 如果当前节点 hash 等于 key 的 hash，并且 equals 相等，当前节点就是我们要找的节点</span>
    <span class="token comment">// 当 hash 冲突时，同一个 hash 值上是一个链表的时候，我们是通过 equals 方法来比较 key 是否相等的</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>e<span class="token punctuation">.</span>hash <span class="token operator">==</span> hash <span class="token operator">&amp;&amp;</span>
        <span class="token punctuation">(</span><span class="token punctuation">(</span>k <span class="token operator">=</span> e<span class="token punctuation">.</span>key<span class="token punctuation">)</span> <span class="token operator">==</span> key <span class="token operator">||</span> <span class="token punctuation">(</span>key <span class="token operator">!=</span> null <span class="token operator">&amp;&amp;</span> key<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>k<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> e<span class="token punctuation">;</span>
    <span class="token comment">// 否则，把当前节点的下一个节点拿出来继续寻找</span>
<span class="token punctuation">}</span> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>e <span class="token operator">=</span> e<span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token operator">!=</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">红黑树查找的代码很多，我们大概说下思路，实际步骤比较复杂，可以去 github 上面去查看源码：</p>
</div><div class="cl-preview-section"><ol>
<li style="font-size: 20px; line-height: 38px;">从根节点递归查找；</li>
<li style="font-size: 20px; line-height: 38px;">根据 hashcode，比较查找节点，左边节点，右边节点之间的大小，根本红黑树左小右大的特性进行判断；</li>
<li style="font-size: 20px; line-height: 38px;">判断查找节点在第 2 步有无定位节点位置，有的话返回，没有的话重复 2，3 两步；</li>
<li style="font-size: 20px; line-height: 38px;">一直自旋到定位到节点位置为止。</li>
</ol>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">如果红黑树比较平衡的话，每次查找的次数就是树的深度。</p>
</div><div class="cl-preview-section"><h2 id="总结" style="font-size: 30px;">总结</h2>
</div><div class="cl-preview-section"><p style="font-size: 20px; line-height: 38px;">HashMap 的内容虽然较多，但大多数 api 都只是对数组 + 链表 + 红黑树这种数据结构进行封装而已，本小节我们从新增和查找两个角度进行了源码的深入分析，分析了是如何对数组、链表和红黑树进行操作的。想了解更多，可以前往 github 上查看更多源码。</p>
</div>}
                        </div>
                    </div>
                                            <!-- 买过的阅读 -->
                        <div class="art-next-prev clearfix">
                                                                                                <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/849">
                                                                    <div class="prev l clearfix">
                                        <div class="icon l">
                                            <i class="imv2-arrow3_l"></i>
                                        </div>
                                        <p>
                                            07 List 源码会问哪些面试题 
                                        </p>
                                    </div>
                                </a>
                                                                                                                            <!-- 已买且开放 或者可以试读 -->
                                    <a href="/read/47/article/851">
                                                                    <div class="next r clearfix">
                                        <p>
                                            09 TreeMap 和 LinkedHashMap 核心源码解析 
                                        </p>
                                        <div class="icon r">
                                            <i class="imv2-arrow3_r"></i>
                                        </div>

                                    </div>
                                </a>
                                                    </div>
                                    </div>
                <div class="comments-con js-comments-con" id="coments_con">
                </div>

                
            </div>
            
            
            

        </div>
    </div>
</div>

<div class="modal modal-jiaQun-new hide" id="modal-jiaQun">
    <div class="inner" style="">
        <div class="modal-close js-close-jiaQun">
            <i class="imv2-close"></i>
        </div>
        <div class="content">
            <img src="https://img4.mukewang.com/5d634d40000119e505400602.jpg">
            <div class="right-info">
                <div class="title">
                    扫码加入慕课Java核心用户群
                </div>
                <div class="desc">
                                            <p class="mb6">验证信息：<span id="joincode">1909271435058473</span><span class="copy js-copy-joincode">复制</span></p>
                                        <p class="mb6">QQ讨论群号：906691736</p>
                                            <p>QQ群URL：<a href="https://jq.qq.com/?_wv=1027&amp;k=55RtSbJ" target="_blank">点击访问</a></p>
                                    </div>
            </div>
            <p class="tip">若遇到搜索不到QQ群或加群失败，请联系客服邮箱:kf@imooc.com</p>
        </div>
    </div>
</div>
 
<!-- 专栏介绍页专栏评价 -->

<!-- 专栏介绍页底部三条评价 -->

<!-- 专栏阅读页弹层目录和介绍页页面目录 -->

<!-- 专栏阅读页发布回复 -->

<!-- 专栏阅读页发布评论 -->

<!-- 专栏阅读页底部评论 -->

<!-- 专栏阅读 单个 评论 -->

<!-- 新增回复和展开三条以外回复 -->

<!-- 立即订阅的弹窗 -->












</div></body></html>